package com.learn.algorithm_may_5;

import com.dataconsruct.ListNode;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 *
 * 旋转链表，https://leetcode-cn.com/problems/rotate-list/
 *
 * Created by QI.
 * 2020/5/14 0:31
 */
public class RotateListNode {

    private static final Logger logger = LoggerFactory.getLogger(RotateListNode.class);

    public static void main(String[] args) {

        int[] arr = {1,2,3,4,5};
//        int[] arr = {1};
        //- 设定 k >= 1
        int k = 4;
        ListNode head = new ListNode(arr[0]);
        ListNode cursor = head;
        for (int i = 1; i < arr.length; i++) {
            cursor.next = new ListNode(arr[i]);
            cursor = cursor.next;
        }

        logger.info("输入：{}, {}", Arrays.toString(arr), String.format("[%s]", k));
        ListNode node = rotateRight(head, k);

        logger.info("输出：{}", node != null ? node.toString() : "[]");
    }

    public static ListNode rotateRightOne(ListNode head, int k) {

        if (head == null || k <= 0){
            return head;
        }
        // 每一次旋转，就是倒数第二个的next指向null，倒数第一个的next指向head
        ListNode cursor = head;
        ListNode prev = head;
        //- 当cursor.next = null时，cursor是最后的节点，prev是倒数第二个节点
        while (cursor.next != null){
            prev = cursor;
            cursor = cursor.next;
        }
        prev.next = null;
        cursor.next = head;
        if (k > 1){
            k--;
            cursor = rotateRightOne(cursor, k);
        }
        return cursor;
    }

    /**
     * 1.计算单向链表的长度length，根据k计算最小旋转次数 k = k % length
     * 2.两个指针分别从1，k+1处计算链表的next，当第二个指针的next = null时，第一个指针处就是分割线，后半部分接上前半部分就是结果
     *
     * @param head 单向链表
     * @param k 旋转次数
     * @return 旋转后的链表
     */
    public static ListNode rotateRight(ListNode head, int k) {
        //- 特殊情况
        if (head == null || k <= 0 ){
            return head;
        }
        ListNode tmp = head;
        int length = 1;
        while (tmp.next != null){
            length++;
            tmp = tmp.next;
        }
        //- 最小旋转次数
        k = k % length;
        if(k == 0){
            return head;
        }
        ListNode cursor = head;
        ListNode prev = head;
        //- 第二个指针cursor比第一个快 k 个
        while (k > 0){
            k--;
            cursor = cursor.next;
        }
        //- 当cursor.next = null时，cursor是最后的节点，prev是分割处的节点（即旋转后的链表的尾部节点）
        while (cursor.next != null){
            prev = prev.next;
            cursor = cursor.next;
        }

        cursor = prev.next;
        prev.next = null;

        //- cursor的尾部的next = head，所以是要遍历到cursor的尾部，再追加head
        tmp = cursor;
        while (tmp.next != null){
            tmp = tmp.next;
        }
        tmp.next = head;

        return cursor;
    }

}

